package com.xiaoyu.sort.basic;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: TODO
 * @author: YuWenYi
 * @create: 2021-04-29 14:13
 **/
public class QuickSort {

    //快速排序做法一:指针交换法  8万数据15毫秒左右,800万数据1秒左右
    //简单描述:pivot开始不变,最后找到了l==r的索引值后,再把pivot的值与该位置的值作交换
    public static void quickSort(int[] arr,int left,int right){
        if (left >= right) {
            return;
        }
        int l = left;
        int r = right;
        int pivot = arr[left];  //取首位作为基准数来切分数组
        int temp;

        //用来将所有在pivot两边的值分在两边
        while ( l < r ){
            //找到数组右边比第一个pivot小的数字时,才退出循环
            while (l < r && arr[r] > pivot)
                r--;

            //找到数组左边比第一个pivot大,才退出循环
            //必须要有等于,因为pivot的位置一开始就是在首位,不能动,直到l==r之后,说明找到了该pivot的位置,然后再交换它的位置即可!
            //假设去掉等于，那么我们从左侧取的第一个值,pivot为左侧第一位的值
            //则arr[l]<pivot条件不成立，那么则l的值就不会变化，此时在下面的交换中，arr[l]的值始终不变，最终的排序结果也将是错误的，所以需要是小于等于基准元素
            while (l < r && arr[l] <= pivot)
                l++;

            if (l < r){  //如果左边有比pivot大的数字,右边有比pivot小的数字,那么就交换他们的位置
                temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;
            }else {
                break;  //如果l>=r,说明整个左边已经没有比pivot大的数字了
            }
        }
        //将pivot的值和指针重合处交换
        arr[left] = arr[l];
        arr[l] = pivot;
        //System.out.println(Arrays.toString(arr));
        //递归进行排序,将分好的子串再进行上面的操作,直到所有的值都排序完成,即传入的left >= right就不进行递归了
        quickSort(arr,left,l-1);
        quickSort(arr,l+1,right);
    }

    //快速排序做法二:挖坑填数法  8万数据18毫秒左右,800万数据1秒左右
    //简单描述:pivot仅用来作比较,真正移动的是hole的值(数坑所在的索引)
    //当l==r之后,即分组完成后,将pivot的值放在最后的坑位上
    public static void quickSort2(int[] arr,int left,int right){
        if (left >= right) {
            return;
        }
        int l = left;
        int r = right;
        int pivot = arr[left];  //取首位作为基准数来切分数组
        int hole = left;   //取pivot的初始位置为首坑位

        while (l < r){
            //如果右边有小于pivot的数字,就将其填到坑位中
            while (l < r){
                if (arr[r] < pivot){
                    arr[hole] = arr[r];  //如果在右边找到了比pivot还小的数字,就将该数字填到坑中
                    hole = r;  //此时r位置为hole新坑位
                    l++;    //由于刚已经将该数字填到坑位中,那么该位置一定是在左边且比pivot小,所以i++防止不必要的比较
                    break;  //结束右边循环
                }
                r--;  //如果没找到,就进行r--,继续向左寻找
            }

            //如果左边有 大于pivot的数字,就将其填到坑位中
            while (l < r){
                if (arr[l] > pivot){
                    arr[hole] = arr[l];  //找到所需的值，将值填充到坑位
                    hole = l; //此时l位置为hole新坑位
                    r--;     //左侧找到了数据之后，right向左移动一位，准备进行比较
                    break;   //结束左边循环
                }
                l++;  //如果没找到,就进行l++,继续向右寻找
            }
        }
        arr[hole] = pivot;   //最后将pivot的值放在坑位上
        //System.out.println(Arrays.toString(arr));
        quickSort2(arr,left,l-1);  //对基准数的左侧进行排序
        quickSort2(arr,l+1,right);  //对基准数的右侧进行排序
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-9,-2,-17,4,6,-20,9,8,-16,50,4,15};
        int[] nums = new int[]{6,9,1,8,2,3,5,4,7,0};
        //quickSort(nums,0,nums.length-1);
        //System.out.println(Arrays.toString(nums));

        //速率测试
        int[] bigData = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            bigData[i] = (int)(Math.random() * 8000000);
        }
        long start = System.currentTimeMillis();
        quickSort2(bigData,0, bigData.length-1);
        long stop = System.currentTimeMillis();

        System.out.println((stop-start)/1000.0); //15毫秒左右

    }
}
